8.2 选择排序

选择排序是一种简单直观的排序算法。其基本思想是在未排序序列中找到最小（或最大）的元素，并将其与未排序序列的第一个元素交换，随后再继续从剩下的未排序序列中找最小（或最大）的元素，重复此操作直到序列有序。

本节代码存放目录为 lesson17

概念与原理

选择排序的原理如下：

• 从未排序序列中找到最小的元素，放到已排序序列的末尾。

• 再从剩下的未排序序列中找到最小的元素，继续放到已排序序列末尾。

• 重复以上步骤，直到所有元素都放入已排序序列。

选择排序的基本特点：

• 时间复杂度为 O(n^2)，无论数组是否有序，每次都需要遍历整个未排序部分。

• 选择排序是不稳定的，因为交换操作可能改变相同元素的相对顺序。

选择排序的步骤示例

给定如下无序数组，按照从小到大排序：

[5, 3, 8, 4, 2]

通过选择排序的步骤如下：

第一轮：

- 从 [5, 3, 8, 4, 2] 中找到最小值 2，交换 arr[0] 和 arr[4]

- 结果：[2, 3, 8, 4, 5]

第二轮：

- 从 [3, 8, 4, 5] 中找到最小值 3，不需要交换

- 结果：[2, 3, 8, 4, 5]

第三轮：

- 从 [8, 4, 5] 中找到最小值 4，交换 arr[2] 和 arr[3]

- 结果：[2, 3, 4, 8, 5]

第四轮：

- 从 [8, 5] 中找到最小值 5，交换 arr[3] 和 arr[4]

- 结果：[2, 3, 4, 5, 8]

最终，排序结果为 [2, 3, 4, 5, 8]

选择排序的时间复杂度

选择排序无论数组的初始状态如何，总是执行 n(n-1)/2 次比较。因此时间复杂度如下：

• 最坏情况：O(n²)

• 最好情况：O(n²)

• 平均情况：O(n²)

选择排序的特点是它总是进行固定数量的比较和交换，无论数组是否已经部分有序。

Go语言的实现

实现代码如下：

func selectionSort(arr []int) {
    length := len(arr)
    num := 0

    // 轮次控制
    for i := 0; i < length-1; i++ {
        fmt.Printf("\n第 %d 轮\n", i+1)

        // 假设当前未排序部分的第一个元素是最小值
        minIndex := i

        // 找到未排序部分的最小元素
        for j := i + 1; j < length; j++ {
            num++
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
            fmt.Printf("第 %d 次比较\n", num)
        }

        fmt.Printf("此轮已排序序列：%v, ", arr[0:i])
        fmt.Printf("此轮未排序序列：%v, ", arr[i:length])

        // 将未排序部分的最小值与当前元素交换
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
        fmt.Printf("此轮比较结果: %v\n", arr)
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    selectionSort(arr)
    fmt.Println("\n排序结果: ", arr)
}

执行结果如下所示：

第 1 轮
第 1 次比较
第 2 次比较
第 3 次比较
第 4 次比较
此轮已排序序列：[], 此轮未排序序列：[5 3 8 4 2], 此轮比较结果: [2 3 8 4 5]

第 2 轮
第 5 次比较
第 6 次比较
第 7 次比较
此轮已排序序列：[2], 此轮未排序序列：[3 8 4 5], 此轮比较结果: [2 3 8 4 5]

第 3 轮
第 8 次比较
第 9 次比较
此轮已排序序列：[2 3], 此轮未排序序列：[8 4 5], 此轮比较结果: [2 3 4 8 5]

第 4 轮
第 10 次比较
此轮已排序序列：[2 3 4], 此轮未排序序列：[8 5], 此轮比较结果: [2 3 4 5 8]

排序结果:  [2 3 4 5 8]

实现选择排序，我们可以理解为：从数组的开始，先遍历一次找到最小的值，将最小的值拿出来，放在数组的头部arr[0]，作为已排序序列，后面的都是未排序序列；下一次再继续从未排序序列找出最小的放到arr[1]，以此类推。

总的来说，就是不断遍历获取最小值，那么未排序的数组就越来越小，直到最终全都遍历完成。

小结

本节我们讲解了选择排序的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：选择排序的时间复杂度为 O(n²)，无论数组初始状态如何。

• 稳定性：选择排序是不稳定的排序算法。

• 应用场景：选择排序适合数据量较小或对排序效率要求不高的场景。